#ifndef HEADER_OF_CHY
#define HEADER_OF_CHY
#define PRINT_WARNING_INFO false
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
#pragma GCC target("avx","sse2")
#include <bits/stdc++.h>


namespace FAST_IO {

} //FAST_IO


namespace BIG_NUMBER {

} //BIG_NUMBER


namespace DATA_STRUCTURE {
	template< typename T1, typename T2 > struct Pair {
		T1 First; T2 Second; 
		Pair() {}
		Pair( T1 _First, T2 _Second ) : First( _First ), Second( _Second ) {}
		bool operator < ( const Pair Other ) const { return First < Other.First || First == Other.First && Second < Other.Second; }
	};
	/*
	template< typename T > struct StackLink {};
	*/
	template< typename T > struct StackArr {
		int Size, MaxSize; T *Arr;
		StackArr() {}
		StackArr( int _Size, int _MaxSize, T *_Arr ) : Size( _Size ), MaxSize( _MaxSize ), Arr( _Arr ) {}
		void Clear() { Size = 0; return; }
		bool IsEmpty() { return Size <= 0; }
		bool IsFull() { return Size >= MaxSize; }
		T Top() { return Arr[ Size - 1 ]; };
		void Pop() { if( Size <= 0 ) { if( PRINT_WARNING_INFO ) printf( "chy.h : Dangerous Operation : StackArr->Pop\n" ); exit( 0 ); } --Size; return; }
		void Push( T E ) { if( Size >= MaxSize ) { if( PRINT_WARNING_INFO ) printf( "chy.h : Dangerous Operatioin : StackArr->Push\n" ); exit( 0 ); } Arr[ Size++ ] = E; return; }
	};
	/*
	template< typename T > struct QueueLink {};
	*/
	template< typename T > struct QueueArr {
		int L, R, MaxSize;
		T *Arr;
		QueueArr() {}
		QueueArr( int _L, int _R, int _MaxSize, T *_Arr ) : L( _L ), R( _R ), MaxSize( _MaxSize ), Arr( _Arr ) {}
		void Clear() { L = R = 0; return; }
		bool IsEmpty() { return L == R; }
		bool IsFull() { return ( L + 1 ) % MaxSize == R; }
		void Push( T E ) {
			if( ( L + 1 ) % MaxSize == R ) { if( PRINT_WARNING_INFO ) printf( "chy.h : Dangerous Operation : QueueArr->Push\n" ); exit( 0 ); }
			L = ( L + 1 ) % MaxSize; Arr[ L ] = E; return;
		}
		T Pop() { 
			if( L == R ) { if( PRINT_WARNING_INFO ) printf( "chy.h : Dangerous Operation : QueueArr->Pop\n" ); exit( 0 ); } 
			L = ( L + 1 ) % MaxSize; return Arr[ ( L - 1 + MaxSize ) % MaxSize ];
		}
	};






	//loj104
	template< typename Type > struct TreapNode { int Random, Size, Cnt; Type Value; TreapNode< Type > *LeftChild, *RightChild; };
	template< typename Type > struct Treap {
		TreapNode< Type > *Root;
		void Collect( TreapNode< Type > *A ) {
			A->Size = A->Cnt + ( ( A->LeftChild != NULL ) ? A->LeftChild->Size : 0 ) + ( ( A->RightChild != NULL ) ? A->RightChild->Size : 0 );
			return;
		}
		TreapNode< Type > *LeftRotate( TreapNode< Type > *A ) {
			TreapNode< Type > *B = A->RightChild; A->RightChild = B->LeftChild; B->LeftChild = A; Collect( A ); Collect( B ); return B;
		}
		TreapNode< Type > *RightRotate( TreapNode< Type > *A ) {
			TreapNode< Type > *B = A->LeftChild; A->LeftChild = B->RightChild; B->RightChild = A; Collect( A ); Collect( B ); return B;
		}
		TreapNode< Type > *Insert( TreapNode< Type > *Rt, Type x ) {
			if( Rt == NULL ) {
				Rt = new TreapNode< Type >; 
				Rt->Random = rand() % 1000000000; Rt->Value = x; Rt->Size = 1; Rt->Cnt = 1; Rt->LeftChild = Rt->RightChild = NULL;
				return Rt;
			}
			++( Rt->Size );
			if( Rt->Value == x ) { ++( Rt->Cnt ); return Rt; }
			if( Rt->Value < x ) { 
				Rt->RightChild = Insert( Rt->RightChild, x ); if( Rt->RightChild->Random < Rt->Random ) Rt = LeftRotate( Rt );
			} else {
				Rt->LeftChild = Insert( Rt->LeftChild, x ); if( Rt->LeftChild->Random < Rt->Random ) Rt = RightRotate( Rt );
			}
			return Rt;
		}
		TreapNode< Type > *Del( TreapNode< Type > *Rt, Type x ) {
			if( Rt == NULL ) { if( PRINT_WARNING_INFO ) printf( "chy.h : Notice : Treap->Delete : No such number called %d\n", x ); return Rt; }
			if( Rt->Value == x ) {
				if( Rt->Cnt > 1 ) { --( Rt->Cnt ); --( Rt->Size ); return Rt; }
				if( Rt->LeftChild == NULL ) { TreapNode< Type > *T = Rt->RightChild; delete Rt; return T; }
				if( Rt->RightChild == NULL ) { TreapNode< Type > *T = Rt->LeftChild; delete Rt; return T; }
				if( Rt->LeftChild->Random <= Rt->RightChild->Random ) {
					Rt = RightRotate( Rt ); --( Rt->Size ); Rt->RightChild = Del( Rt->RightChild, x ); return Rt;
				} else {
					Rt = LeftRotate( Rt ); --( Rt->Size ); Rt->LeftChild = Del( Rt->LeftChild, x ); return Rt;
				}
				return Rt;
			}
			--( Rt->Size );
			if( Rt->Value < x ) { Rt->RightChild = Del( Rt->RightChild, x ); return Rt; } else { Rt->LeftChild = Del( Rt->LeftChild, x ); return Rt; }
			return Rt;
		}
		int QueryR( TreapNode< Type > *Rt, Type x ) {
			int Ans = 0;
			for( ; Rt != NULL; ) {
				if( Rt->Value == x ) return Ans + ( ( Rt->LeftChild != NULL ) ? Rt->LeftChild->Size : 0 ) + 1;
				if( Rt->Value < x ) { Ans += ( ( Rt->LeftChild != NULL ) ? Rt->LeftChild->Size : 0 ) + Rt->Cnt; Rt = Rt->RightChild; } else Rt = Rt->LeftChild;
			}
			return Ans + 1;
		}
		Type QueryN( TreapNode< Type > *Rt, int x ) {
			for( ; Rt != NULL; ) {
				int Rc = 0; if( Rt->LeftChild != NULL ) Rc = Rt->LeftChild->Size;
				if( x > Rc && x <= Rc + Rt->Cnt ) return Rt->Value;
				if( x <= Rc ) Rt = Rt->LeftChild; else { x -= Rc + Rt->Cnt; Rt = Rt->RightChild; }
			}
			if( PRINT_WARNING_INFO ) printf( "chy.h : Notice : Treap->QueryNumber Failed.\n" );
			return -1;
		}
		Type pre( TreapNode< Type > *Rt, Type x ) {
			int Ans = x;
			for( ; Rt != NULL; ) if( Rt->Value < x ) { Ans = Rt->Value; Rt = Rt->RightChild; } else Rt = Rt -> LeftChild;
			if( Ans == x ) if( PRINT_WARNING_INFO ) printf( "chy.h : Notice : Treap->Query Pre Failed.\n" );
			return Ans;
		}
		Type suc( TreapNode< Type > *Rt, Type x ) {
			int Ans = x;
			for( ; Rt != NULL; ) if( Rt->Value > x ) { Ans = Rt->Value; Rt = Rt->LeftChild; } else Rt = Rt -> RightChild;
			if( Ans == x ) if( PRINT_WARNING_INFO ) printf( "chy.h : Notice : Treap->Query Suc Failed.\n" );
			return Ans;
		}
		void clear() { delete [] Root; Root = NULL; srand( time( NULL ) ); return; }
		void insert( Type x ) { Root = Insert( Root, x ); return; }
		void Delete( Type x ) { Root = Del( Root, x ); return; }
		int QueryRank( Type x ) { return QueryR( Root, x ); }
		Type QueryNumber( int x ) { return QueryN( Root, x ); }
		Type Pre( Type x ) { return pre( Root, x ); }
		Type Suc( Type x ) { return suc( Root, x ); }
	};








	//luogu3690
	//loj2245
	struct LCTChild {
		int Child[ 2 ];
	};
	struct LCT {
		int *Father, *Stack, *Tag;
		LCTChild *Child;
		LCT() {}
		LCT( int *_Father, LCTChild *_Child, int *_Stack, int *_Tag ) : Father( _Father ), Child( _Child ), Stack( _Stack ), Tag( _Tag ) {}
		void Clear() { memset( Father, 0, sizeof( Father ) ); memset( Tag, 0, sizeof( Tag ) ); memset( Child, 0, sizeof( Child ) ); return; }
		void Collect( int Index );
		void TagDown( int x );
		bool IsRoot( int x ) { return !( ( Child[ Father[ x ] ].Child[ 0 ] == x ) || ( Child[ Father[ x ] ].Child[ 1 ] == x ) ); }
		void Rotate( int C ) {
			int B = Father[ C ]; int A = Father[ B ]; int Tag = Child[ B ].Child[ 1 ] == C;
			if( !IsRoot( B ) ) Child[ A ].Child[ Child[ A ].Child[ 1 ] == B ] = C; Father[ C ] = A;
			Father[ Child[ C ].Child[ Tag ^ 1 ] ] = B; Child[ B ].Child[ Tag ] = Child[ C ].Child[ Tag ^ 1 ];
			Child[ C ].Child[ Tag ^ 1 ] = B; Father[ B ] = C;
			Collect( B ); Collect( C );
			return;
		}
		void Splay( int x ) {
			int Num = 0; Stack[ ++Num ] = x; int t = x; for( ; !IsRoot( t ); t = Father[ t ] ) Stack[ ++Num ] = Father[ t ]; for( int i = Num; i >= 1; --i ) TagDown( Stack[ i ] );
			while( !IsRoot( x ) ) { 
				int y = Father[ x ]; int z = Father[ y ]; if( !IsRoot( y ) ) if( ( Child[ z ].Child[ 0 ] == y ) ^ ( Child[ y ].Child[ 0 ] == z ) ) Rotate( x ); else Rotate( y ); Rotate( x );
			}
			Collect( x );
			return;
		}
		void Access( int x ) { for( int i = 0; x; i = x, x = Father[ x ] ) { Splay( x ); Child[ x ].Child[ 1 ] = i; Collect( x ); } return; }
		void MakeRoot( int x ) { Access( x ); Splay( x ); Tag[ x ] ^= 1; return; }
		int FindRoot( int x ) { Access( x ); Splay( x ); TagDown( x ); while( Child[ x ].Child[ 0 ] ) { x = Child[ x ].Child[ 0 ]; TagDown( x ); } Splay( x ); return x; }
		void Split( int x, int y ) { MakeRoot( x ); Access( y ); Splay( y ); return; }
		void Link( int x, int y ) { MakeRoot( x ); if( FindRoot( y ) == x ) return; Father[ x ] = y; return; }
		void Cut( int x, int y ) { MakeRoot( x ); if( FindRoot( y ) != x || Child[ y ].Child[ 0 ] || Father[ y ] != x ) return; Father[ y ] = Child[ x ].Child[ 1 ] = 0; Collect( x ); return; }
	};
} //DATA_STRUCTURE

namespace GEOMETRY {
} //GEOMETRY


/*
//The Follow Function Needed

void DATA_STRUCTURE::LCT::Collect( int Index ) { return; }
//Sum[ Index ] = Sum[ Child[ Index ].Child[ 0 ] ] ^ Sum[ Child[ Index ].Child[ 1 ] ] ^ Value[ Index ]; 

void DATA_STRUCTURE::LCT::TagDown( int x ) {
	if( Tag[ x ] ) { 
		Tag[ x ] = 0; 
		std::swap( Child[ x ].Child[ 0 ], Child[ x ].Child[ 1 ] );
		Tag[ Child[ x ].Child[ 0 ] ] ^= 1; Tag[ Child[ x ].Child[ 1 ] ] ^= 1; 
	} 
	return;
}
*/

#endif